template<class K>
struct BSTreeNode {
    BSTreeNode<K> *_left;
    BSTreeNode<K> *_right;
    K _key;

    BSTreeNode(const K &key)
            : _left(nullptr), _right(nullptr), _key(key) {}
};

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    BSTree() = default; //制定强制生成默认构造

    BSTree(const BSTree<K>& t)
    {
        _root = Copy(t._root);
    }

    BSTree<K>& operator=(BSTree<K> t)
    {
        swap(_root, t._root);
        return *this;
    }

    ~BSTree()
    {
        Destroy(_root);
        //_root = nullptr;
    }
    bool Insert(const K &key)
    {
        if (_root == nullptr)
        {
            _root = new Node(key);
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur)
        {
            if (key > cur->_key)//插入值大于key时，往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (key < cur->_key)//插入值小于key时，往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(key);//新建插入值节点
        // 链接
        if (key > parent->_key)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }

        return true;
    }

    Node *Find(const K &key)
    {
        Node* cur = _root;
        while (cur)
        {
            if (key > cur->_key)
            {
                cur = cur->_right;
            }
            else if (key < cur->_key)
            {
                cur = cur->_left;
            }
            else
            {
                return cur;
            }
        }

        return nullptr;
    }

    bool Erase(const K &key)
    {
        Node* parent = _root;
        Node* cur = _root;

        while (cur)
        {
            if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                // 删除
                // 1、左为空
                if (cur->_left == nullptr)
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_right;
                    }
                    else
                    {
                        parent->_right = cur->_right;
                    }

                    delete cur;

                } // 2、右为空
                else if (cur->_right == nullptr)
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }

                    delete cur;
                }
                else//2种方案:
                // 1.左子树中找最大的，即找到左子树然后一直向右查找（因为右子树一定比根大）
                //2.右子树中找最小的，即找到右子树然后一直向左查找（因为左子树一定比根小)
                //这里采用从右子树中找最小的
                {
                    Node* prev=cur;
                    Node* minRight=cur->_right;
                    while(minRight->_left)
                    {
                        prev=minRight;
                        minRight=minRight->_left;
                    }
                    swap(cur->_key,minRight->_key);
                    if(prev->_left==minRight)
                    {
                        prev->_left=minRight->_right;
                    }
                    else
                    {
                        prev->_right=minRight->_right;
                    }
                    delete minRight;
                }

                return true;
            }
        }

        return false;
    }

    bool FindR(const K& key)
    {
        return _FindR(_root, key);
    }

    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }

    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }
protected:
    Node* Copy(Node* root)//拷贝
    {
        if (root == nullptr)
            return nullptr;

        Node* newRoot = new Node(root->_key);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    void Destroy(Node*& root)//删除
    {
        if (root == nullptr)
            return;

        Destroy(root->_left);
        Destroy(root->_right);

        delete root;
        root = nullptr;
    }

    bool _FindR(Node* root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (root->_key == key)
            return true;

        if (key > root->_key)
            return _FindR(root->_right, key);
        else
            return _FindR(root->_left, key);
    }

    bool _EraseR(Node*& root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (key > root->_key)
        {
            return _EraseR(root->_right, key);
        }
        else if (key < root->_key)
        {
            return _EraseR(root->_left, key);
        }
        else
        {
            Node* del = root;//标记删除节点
            //其中一个为空时
            if (root->_right == nullptr)
            {
                root = root->_left;//右为空继承左边，左也为空时直接=nullptr
            }
            else if (root->_left == nullptr)
            {
                root = root->_right;//左为空继承右边，右也空直接=nullptr
            }
            else//两边都不为空
            {
                Node* maxleft = root->_left;
                while (maxleft->_right)//找到左子树最大的右值
                {
                    maxleft = maxleft->_right;
                }
                swap(root->_key, maxleft->_key);
                return _EraseR(root->_left, key);
            }
            delete del;

            return true;
        }
    }

    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }


private:
    Node *_root = nullptr;
};



namespace key_value
{
#pragma once

    // BinarySearchTree -- BSTree
    // SearchBinaryTree


    template<class K, class V>
    struct BSTreeNode
    {
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
        K _key;
        V _value;


        BSTreeNode(const K& key, const V& value)
                :_left(nullptr)
                , _right(nullptr)
                , _key(key)
                , _value(value)
        {}
    };

    template<class K, class V>
    class BSTree
    {
        typedef BSTreeNode<K, V> Node;
    public:

        bool Insert(const K& key, const V& value)
        {
            if (_root == nullptr)
            {
                _root = new Node(key, value);
                return true;
            }

            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }

            cur = new Node(key, value);
            // 链接
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }

            return true;
        }

        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }

            return nullptr;
        }
        bool Erase(const K &key)
        {
            Node* parent = _root;
            Node* cur = _root;

            while (cur)
            {
                if (key > cur->_key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (key < cur->_key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    // 删除
                    // 1、左为空
                    if (cur->_left == nullptr)
                    {
                        if (parent->_left == cur)
                        {
                            parent->_left = cur->_right;
                        }
                        else
                        {
                            parent->_right = cur->_right;
                        }

                        delete cur;

                    } // 2、右为空
                    else if (cur->_right == nullptr)
                    {
                        if (parent->_left == cur)
                        {
                            parent->_left = cur->_left;
                        }
                        else
                        {
                            parent->_right = cur->_left;
                        }

                        delete cur;
                    }
                    else//2种方案:
                        // 1.左子树中找最大的，即找到左子树然后一直向右查找（因为右子树一定比根大）
                        //2.右子树中找最小的，即找到右子树然后一直向左查找（因为左子树一定比根小)
                        //这里采用从右子树中找最小的
                    {
                        Node* prev=cur;
                        Node* minRight=cur->_right;
                        while(minRight->_left)
                        {
                            prev=minRight;
                            minRight=minRight->_left;
                        }
                        swap(cur->_key,minRight->_key);
                        if(prev->_left==minRight)
                        {
                            prev->_left=minRight->_right;
                        }
                        else
                        {
                            prev->_right=minRight->_right;
                        }
                        delete minRight;
                    }

                    return true;
                }
            }

            return false;
        }

        void InOrder()
        {
            _InOrder(_root);
//            cout << endl;
        }

    protected:
        void _InOrder(Node* root)
        {
            if (root == nullptr)
                return;

            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}